import java.util.Random;

public class findKthLargest {
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums,0,nums.length-1,k);
    }
    public int qsort(int[] nums,int l,int r,int k){
        if(l==r){
            return nums[l];
        };
        int ret= nums[new Random().nextInt(r - l + 1)+l];
        int i=l;
        int left=l-1;
        int right=r+1;
        while(i<right){
            if(nums[i]<ret) swap(nums,++left,i++);
            else if(nums[i]==ret) i++;
            else swap(nums,--right,i);
        }
        int c=r-right+1;int b=right-left-1;
        if(c>=k) return qsort(nums,right,r,k);
        else if(c+b>=k) return ret;
        else return qsort(nums,l,left,k-b-c);
    }
    public void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}
